# 《旋转矩阵》
# 原题链接：https://leetcode.cn/leetbook/read/array-and-string/clpgd/

# 需求分析：
# 1、给定一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。
# 2、设计一种算法，将图像旋转 90 度。
# 3、不占用额外内存空间能否做到？

# 示例 1:
# 给定 matrix =
# [
#     [1, 2, 3],
#     [4, 5, 6],
#     [7, 8, 9]
# ],
# 原地旋转输入矩阵，使其变为:
# [
#     [7, 4, 1],
#     [8, 5, 2],
#     [9, 6, 3]
# ]

# 示例 2:
# 给定 matrix =
# [
#     [5, 1, 9, 11],
#     [2, 4, 8, 10],
#     [13, 3, 6, 7],
#     [15, 14, 12, 16]
# ],
# 原地旋转输入矩阵，使其变为:
# [
#     [15, 13, 2, 5],
#     [14, 3, 4, 1],
#     [12, 6, 8, 9],
#     [16, 7, 10, 11]
# ]

# 思路1：逐列拷贝，逐行赋值

# 思路2：利用矩阵的翻转实现矩阵的旋转
# 设二维数组（矩阵）各元素为a[i][j]，将矩阵顺时针旋转90度
# 1、主对角线（左上右下）翻转一次
#    交换i，j的值得到目的索引，swap交换
# 2、水平（沿y轴）翻转一次
#    n-1-j获取目的列，逐列swap交换


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix)
        for i in range(length):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for j in range(length // 2):
            for i in range(length):
                matrix[i][j], matrix[i][length - 1 - j] = (
                    matrix[i][length - 1 - j],
                    matrix[i][j],
                )


# 思路一优化
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix)
        for i in range(length):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(length):
            matrix[i] = matrix[i][::-1]


# 内置函数
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 解压相当于对角线互换
        matrix[:] = zip(*matrix[::-1])
        # zip(*m)相当于下述操作
        # def myzip(matrix):
        #     martix_new = [[]]
        #     for j in range(len(matrix[0])):
        #         temp = []
        #         for i in range(len(matrix)):
        #             temp.append(matrix[i][j])
        #         martrix_new.append(temp)
        #     matrix = martix_new


# 示例代码：数学推导
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        matrix_new = [[0] * n for k in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n - i - 1] = matrix[i][j]
        matrix[:] = matrix_new
